It is assumed that $|M|=|N|=n$ because the problem has feasible solutions only if this is the case. Then the problem amounts to finding a permutation matrix $\vc{x}$ that fulfills the budget constraint and maximizes the cost function. We will denote the predicates that constraints \eqref{ex8:con1}, \eqref{ex8:con2} and~\eqref{ex8:con3} hold with $S_1(\vc{x})$, $S_2(\vc{x})$ and $B(\vc{x})$ respectively.

We will first discuss the strength of all combinations of Lagrangian relaxations before dealing with the difficulty of solving the resulting subproblems and the LD problem.

The conclusion regarding the strength of Lagrangian relaxations is that $z^{\LP} = w_{LD}$ iff the budget constraint is dualized. To show this, we look at the cases in which the budget constraint is not dualized first and prove that equality does not hold:
\begin{itemize}
\item In the case that only constraint~\eqref{ex8:con2} is dualized, we have to disprove
	$$ \conv(\{\vc{x} \in \{0,1\}^{n \times n} : S_1(\vc{x}), B(\vc{x})\}) = \{\vc{x} \in [0,1]^{n \times n} : S_1(\vc{x}), B(\vc{x})\}. $$
	
The following LP is a counter example: $n=2$, $4x_{11}+x_{12}+4x_{21}+x_{22} \le 3$. Then the set on the left side of the equation consists only of $\begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$. The set on the right hand contains $\begin{pmatrix} 0.1 & 0.9 \\ 0.1 & 0.9 \end{pmatrix}$.
\item If only constraint~\eqref{ex8:con1} is dualized, the counter example can be transposed.
\item If both constraints \eqref{ex8:con1} and~\eqref{ex8:con2} are dualized, the counter example works as well. The set on the left side of the equation is $\conv \left( \left\{ \begin{pmatrix} 0 & i_1 \\ 0 & i_2 \end{pmatrix} : i_1, i_2 \in \{	0,1\} \right\} \right)$ and does not contain $\begin{pmatrix} 0.1 & 0.9 \\ 0.1 & 0.9 \end{pmatrix}$.
\end{itemize}

It is left to show that $z^{\LP} = w_{LD}$ if the budget constraint is dualized:
\begin{itemize}
	\item If only the budget constraint is dualized, we have to show that
	$$ \conv(\{\vc{x} \in \{0,1\}^{n \times n} : S_1(\vc{x}), S_2(\vc{x})\}) = \{\vc{x} \in [0,1]^{n \times n} : S_1(\vc{x}), S_2(\vc{x})\}, $$
	or in other words, that the set of doubly stochastic matrices equals the convex hull of permutation matrices. This is known as the Birkhoff--von Neumann theorem and is a standard proof in combinatorics.
	\item If exactly one of the constraints \eqref{ex8:con1} or~\eqref{ex8:con2} is dualized as well, the situation is similar. We have to show that the set of right (left) stochastic matrices is the convex hull of 0-1 matrices whose rows (columns) sum to 1. This is easy to see by considering the following algorithm (here for sum 1 rows):
	\begin{enumerate}
		\item Init: $i=0$.
		\item Find $r_1,\ldots,r_n$, the row maxima of the matrix $S$. Let $\lambda_i=\min_k r_k$.
		\item Let $C_i$ denote the $n \times n$-matrix with 1's at the positions were the row maxima were found and 0's elsewhere. Set $S:=S-\lambda_iC_i.$
		\item Stop if S = 0, otherwise set $i:=i+1$ and go to (b).
	\end{enumerate}
	Proof of correctness: The convex coefficients $\lambda_1,\ldots,\lambda_m$ are chosen in step (c), the matrices with non-zero coefficients $C_1,\ldots, C_m$ are chosen in step (b). The elements in $S$ stay non-negative by construction of $\lambda_i$. The sum of all elements in the initial matrix $S$ equals $n$. The sum of all elements in every $C_i$ also equals $n$. Therefore $\sum_{i=0}^m \lambda_i \le 1$. At least one element in $S$ is set to 0 in every iteration of the algorithm, therefore it terminates in at most $n^2$ steps with $S=0$. It follows that $\sum_{i=0}^m \lambda_i = 1$ and that $\sum_{i=0}^m \lambda_i C_i=S$ is a convex combination.
	\item If all three constraints are dualized, we are left with
		$$ \conv(\{\vc{x}: \vc{x} \in \{0,1\}^{n \times n}\}) = \{\vc{x}: \vc{x} \in [0,1]^{n \times n}\}, $$
	which is trivially true.
\end{itemize}

Ease of solving the Lagrangian subproblems:
\begin{itemize}
	\item If only the budget constraint is dualized, we are still left with a linear assignment problem which is difficult to solve.
	\item If exactly one of constraints \eqref{ex8:con1} and~\eqref{ex8:con2} are dualized, we are left with a problem that is very similar to the Generalized Assignment Problem, but with a global budget instead of per-machine budgets. This is still difficult to solve.
	\item If both constraints \eqref{ex8:con1} and~\eqref{ex8:con2} are dualized, we are left with a 0-1 knapsack problem, which is solvable in pseudo polynomial time.
	\item If the budget constraint and constraint \eqref{ex8:con1} are dualized, we arrive at IP($\vc{u},v$):
		\begin{align}
			z(\vc{u},v) = \max \quad \sum_{i \in M} \sum_{j \in N} (c_{ij}-u_i-va_{ij})x_{ij} + \sum_{i \in M} u_i + vb & \\
			\sum_{i \in M} x_{ij} &= 1 & \forall j \in N \\
			\vc{x} & \in \{0,1\}^{n \times n}
		\end{align}
	This problem can be split into subproblems along the elements of $N$ and solved by inspection. The solution is
		\begin{equation}
			z(\vc{u},v) = \sum_{j \in N} \max_{i \in M} (c_{ij}-u_i-va_{ij}) + \sum_{i \in M} u_i + vb.
		\end{equation}
	\item If all three constraints are dualized the solution is similarly easy to solve:
		\begin{equation}
			z(\vc{u},\vc{v},w) = \sum_{i \in M} \sum_{j \in N} \max \{c_{ij}-u_i-v_j-wa_{ij}, 0 \} + c(\vc{u},\vc{v},w).
		\end{equation}
\end{itemize}

The resulting LD problems have a different number of variables depending on which constraints are dualized. Constraints \eqref{ex8:con1} and~\eqref{ex8:con2} yield $n$ variables each, while the budget constraint yields only one variable.

In conclusion we see that not dualizing the budget constraint yields potentially tighter bounds than the LP relaxations, but at the cost of LD problems that are more difficult to solve.

If the budget constraint is dualized (and possibly one additional constraint), we have $w_{\LD} = z^{\LP}$ but the LD problem contains contain only $n+1$ real variables and evaluating $z(\vc{u},v)$ is a cheap operation. The LP relaxation on the other hand has $n^2$ variables and thus it might be better to opt for the LD instead.